/**
 * 
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），
 * 返回其最大和。
 * 子数组是数组中的一个连续部分。
 * 1 <= nums.length <= 105
 * -104 <= nums[i] <= 104
 */

 class Solution {
public:
    //method 1
    int maxSubArray(vector<int>& nums) {
        int pre = 0,ans = nums[0];
        for(const auto& x: nums){
            pre = max(pre + x,x);
            ans = max(ans,pre);
        }
        return ans;
    }
    //method 2
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0],sum = 0;
        for(int i = 0;i < nums.size();i++){
            sum += nums[i];
            ans = max(ans,sum);
            if(sum < 0){
                sum = 0;
            }
        }
        return ans;
    }
};